package merge;

public class Merge01 {
    public static void sort(int[] arr,int left,int right){
        if (left >= right)return;
        int mid = left + (right - left) / 2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        merge(arr,left,mid+1,right);
    }

    public static void merge(int[] arr,int left,int mid,int right){
        int[] temp = new int[right - left + 1];
        int index = 0;
        int i = left;
        int j = mid;
        while(i < mid && j <= right){
            if(arr[i] < arr[j]){
                temp[index++] = arr[i++];
            }else{
                temp[index++] = arr[j++];
            }
        }
        while (i < mid){
            temp[index++] = arr[i++];
        }
        while (j <= right){
            temp[index++] = arr[j++];
        }
        index = 0;
        for (int k = left; k <= right; k++) {
            arr[k] = temp[index++];
        }
    }
}
